package com.cuz.daileetcode;

/**
 * @author cuzz
 * @version 1.0
 * @description: 41. 缺失的第一个正数
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * 示例 1：
 * 输入：nums = [1,2,0]
 * 输出：3
 * 示例 2：
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 * 示例 3：
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 * 提示：
 * 1 <= nums.length <= 5 * 105
 * -231 <= nums[i] <= 231 - 1
 * @date 21:33 2021/10/5
 **/
public class Day17 {

    static class S1 {
        public static void main(String[] args) {
            System.out.println(firstMissingPositive(new int[]{1}));
        }

        public static int firstMissingPositive(int[] nums) {
            //3,4,-1,1
            //遍历一次数组 判断1 是否存在 不存在返回1 否则将负数和0转化为1
            boolean isOneExist = false;
            for (int index = 0; index < nums.length; index++) {
                if (nums[index] == 1) {
                    isOneExist = true;
                }
                if (nums[index] <= 0) {
                    nums[index] = 1;
                }
            }
            if (!isOneExist) {
                return 1;
            }
            //到这里 为 3 4 1 1，遍历一个数比如3 将num[3]置为绝对值后的负数 即num[3]=-abs(num[3])
            for (int index = 0; index < nums.length; index++) {
                int tempValue = Math.abs(nums[index]);
                if (tempValue <= nums.length) {
                    nums[tempValue - 1] = -Math.abs(nums[tempValue - 1]);
                }
            }
            // -3 4 -1 -1 再次遍历数组 第一个正数的下标为第一个没有出现的整数
            //刚全都是负数 那么返回 数组长度加1
            for (int index = 0; index < nums.length; index++) {
                if (nums[index] > 0) {
                    return index + 1;
                }
            }
            return nums.length + 1;
        }
    }

    static class S2 {
        public int firstMissingPositive(int[] nums) {
            for (int index = 0; index < nums.length; index++) {
                while (nums[index] > 0 && nums[index] <= nums.length && nums[nums[index] - 1] != nums[index]) {
                    int temp = nums[nums[index] - 1];
                    nums[nums[index] - 1] = nums[index];
                    nums[index] = temp;
                }
            }
            for (int index = 0; index < nums.length; index++) {
                if (nums[index] != index + 1) {
                    return index + 1;

                }
            }
            return nums.length + 1;
        }
    }
}
